package com.leetcode.hot100;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-23  19:42
 * @Description: TODO
 * @Version: 1.0
 */
public class 滑动窗口最大值_239 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        int[] ints = new int[nums.length - k + 1];
        for (int right = 0; right < nums.length; right++) {
            while (!queue.isEmpty() && nums[right] >= nums[queue.peekLast()]) {
                queue.removeLast();
            }
            queue.addLast(right);
            int left = right - k + 1;

            if (queue.peekFirst() < left) {
                queue.removeFirst();
            }
            if (right + 1 >= k) {
                ints[left] = nums[queue.peekFirst()];
            }

        }
        return ints;
    }
}
